package linkedlist.leetcode_0204;

/**
 * 分割链表
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null){
            return null;
        }
        ListNode smallHead = null;
        ListNode smallTail = null;
        ListNode equalHead = null;
        ListNode equalTail = null;
        ListNode bigHead = null;
        ListNode bigTail = null;
        ListNode temp =null;
        while (head != null){
            temp = head.next;
            //将节点断链，重新排
            head.next = null;
            if (head.val < x){
                //如果小于区头节点==null，说明此时小于还没有节点，将新节点加入
                if (smallHead == null){
                    smallHead = head;
                    smallTail = head;
                }else {
                    //否则，小于区已经存在节点，将新节点插入小于区尾部
                    smallTail.next = head;
                    smallTail = head;
                }
            }else if (head.val == x){
                if (equalHead == null){
                    equalHead = head;
                    equalTail = head;
                }else {
                    equalTail.next = head;
                    equalTail = head;
                }
            }else {
                if(bigHead == null){
                    bigHead = head;
                    bigTail = head;
                }else {
                    bigTail.next = head;
                    bigTail = head;
                }
            }
            head = temp;
        }

        //对小于区、等于区、大于区是否存在进行判断
        if (smallTail != null){ //小于区存在
            smallTail.next = equalHead;

            //此时要判断等于区是否存在，因为如果等于区不存在，就要让小于区的尾去连大于区的头
            if (equalTail == null){
                smallTail.next = bigHead;
            }
        }
        if(equalTail != null){
            equalTail.next = bigHead;
        }
        //
        return smallHead != null ? smallHead : (equalHead != null ? equalHead : bigHead);
    }
}
